package arrayPractice;
import java.util.Deque;
import java.util.LinkedList;
public class Class977 {
    class Solution {
        public int[] sortedSquares(int[] nums) {
            if (nums.length == 0) {
                return null;
            }
            if (nums.length == 1) {
                return new int[]{nums[0] * nums[0]};
            }
            Deque<Integer> stack = new LinkedList<>();
            if (nums[0] < 0) {
                stack.push(Math.abs(nums[0]));
            } else {
                stack.push(nums[0]);
            }
            int index = 0;
            for (int i = 1; i < nums.length; i++) {
                int cur = Math.abs(nums[i]);
                int top = stack.peek();
                if (cur <= top) {
                    stack.push(cur);
                } else {
                    while (!stack.isEmpty() && cur > stack.peek()) {
                        int value = stack.pop();
                        nums[index++] = value * value;
                    }
                    stack.push(cur);
                }
            }
            nums[nums.length - 1] *= nums[nums.length - 1];
            return nums;
        }
        public int[] sortedSquares1(int[] nums) {
            int slow = 0;
            int fast = nums.length - 1;
            while (slow < fast) {
                if (nums[slow] * nums[slow] < nums[fast] * nums[fast]) {
                    int temp1 = nums[slow] * nums[slow];
                    int temp2 = nums[fast] * nums[fast];
                    nums[slow++] = temp1;
                    nums[fast--] = temp2;
                } else if (nums[slow] * nums[slow] > nums[fast] * nums[fast]) {
                    int temp1 = nums[slow] * nums[slow];
                    int temp2 = nums[fast] * nums[fast];
                    nums[fast--] = temp1;
                    nums[slow++] = temp2;
                } else if (nums[slow] * nums[slow] > nums[fast] * nums[fast]) {
                    int temp1 = nums[slow] * nums[slow];
                    nums[fast--] = temp1;
                    nums[fast--] = temp1;
                    slow++;
                }
            }
            return nums;
        }

        public int[] sortedSquares2(int[] nums) {
            
            int right = nums.length - 1;
            int left = 0;
            int[] result = new int[nums.length];
            int index = result.length - 1;

            while (left <= right) {
                if (nums[left] * nums[left] > nums[right] * nums[right]) {
                    // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
                    result[index--] = nums[left] * nums[left];
                    ++left;
                } else {
                    result[index--] = nums[right] * nums[right];
                    --right;
                }
            }

            return result;

        }







    }
    public static void main(String[] args) {
        Solution solution = new Class977().new Solution();
        int[] arr = {-5, -3, -2, -1};
        int[] ints = solution.sortedSquares(arr);
        for (int a : ints
        ) {
            System.out.println(a);
        }
    }
}
